// ==================================================
// Programmer:  Jonathan Landrum
// Date:        6 February 2012
// ==================================================
// Program:     nthPrime.cpp
// Purpose:     Finds the nth prime number.
// Assumptions: 1.) Input is in natural number form
//                  (primes are only natural numbers)
// ==================================================

#include <iostream>
using namespace std;



// --------------------------------------------------
// Function Prototypes
// --------------------------------------------------
bool prime (int);



// --------------------------------------------------
// main():
// Calls the prime() function to find primes, and
// returns the nth prime (as specified by the user.)
// --------------------------------------------------
int main () {
	
	// ------------------------------------------
	// Declare variables, not war
	// ------------------------------------------
	int counter = 1;
	int n = 0;
	int out = 0;
	
	// ------------------------------------------
	// Introduce the program
	// ------------------------------------------
	cout << endl;
	cout << "------------------------------" << endl;
	cout << "-    nth Prime Calculator    -" << endl;
	cout << "------------------------------" << endl;
	cout << endl;
	cout << "This program finds the nth" << endl;
	cout << "prime number." << endl;
	cout << endl;
	cout << "Which prime would you like to" << endl;
	cout << "find? Enter an integer: ";
	cin  >> n;
	cout << endl;
	
	// ------------------------------------------
	// Main processing loop
	// ------------------------------------------
	out = 2;
	while (counter < n) {
		out++;
		if (prime(out)) {
			counter++;
		} // End if
	} // End while
	
	// ------------------------------------------
	// Return the results
	// ------------------------------------------
	cout << out << " is the " << n << "th prime." << endl;
	
	return (0);
} // End main



// --------------------------------------------------
// prime():
// Determines if a number is prime
// --------------------------------------------------
bool prime (int n) {
	
	// Variables
	bool result;
	int  i;
	
	// Do work
	if (n <= 1) {
		result = false; // 1 is not prime
		
	} else if ((n == 2) || (n == 3)) {
		result = true; // Hard code 2 and 3
		
	} else if (n % 2 == 0) {
		result = false; // Get rid of evens
		
	/* All other cases are out, so now we check
	   to see if n is divisible by the odd
	   numbers from 3 on. */
	} else {
		i = 3;
		result = true; // Assume it's prime, then prove
		
		while (true) {
			/* If i^2 is not a root of n, or if
			   n % i == 0. (Won't be larger than
			   the square.) */
			if ((i * i > n) || (n % i == 0))
				break;
			i += 2; // Iterate by 2 to get odds
		} // End while
		
		// Record the answer
		if (i * i > n)
			result = true;
		else
			result = false;
	} // End if
	
	
	// Return the answer
	return result;
}
